package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/09/08 11:30
 **/
public class Day6_4_Num124_MaxPathSum {
    class Solution {
        int max = Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
            dfs(root);
            return max;
        }
        private int dfs(TreeNode root){
            if(root == null) return 0;
            int val = root.val;
            int left = Math.max(0, dfs(root.left));
            int right = Math.max(0, dfs(root.right));
            max = Math.max(max, val+left+right);
            return Math.max(left, right) + val;
        }
    }
}